iT邦幫忙

0

資料結構與演算法[3] - List和SortedList與BinarySearch

  • 分享至 

  • xImage
  •  

比對List和SortedList

比對容器

  • List
  • SortedList

比較方法

  • 資料放入容器的時間
  • 演算法處理時間

開始測試

演算法 - Binary Search

List

public static int Search_List(List<int> list, int num)
{
    int left = 0, right = list.Count() - 1;
    while (left <= right)
    {
        int middle = (right + left) / 2;

        if (list[middle] == num)
            return middle;

        if (list[middle] > num)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return -1;
}

SortedList

public static int Search_SortedList(SortedList<int, int> sortedSet, int num)
{
    int left = 0, right = sortedSet.Count() - 1;
    while (left <= right)
    {
        int middle = (right + left) / 2;

        if (sortedSet.Keys[middle] == num)
            return middle;

        if (sortedSet.Keys[middle] > num)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return -1;
}

測試流程

List

static void ListTest(int testNumber, int targetNumber)
{
    Console.WriteLine("=====List Test=====");
    List<int> list = new List<int>();
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    for (int i = testNumber; i >= 0; i--)
    {
        list.Add(i);
    }
    stopwatch.Stop();
    Console.WriteLine($"Add data cost time : {stopwatch.ElapsedMilliseconds}");

    stopwatch.Restart();
    list.Sort();
    var data = BinarySearcher.Search_List(list, targetNumber);
    stopwatch.Stop();

    Console.WriteLine($"Find Result = {data}");
    Console.WriteLine($"Search Time : {stopwatch.ElapsedMilliseconds}ms");
}

SortedList

static void SortedListTest(int testNumber, int targetNumber)
{
    Console.WriteLine("=====SortedList Test=====");
    Stopwatch stopwatch = new Stopwatch();
    SortedList<int, int> sortedList = new SortedList<int, int>();
    stopwatch.Start();
    for (int i = testNumber; i >= 0; i--)
    {
        sortedList.Add(i, i);
    }
    stopwatch.Stop();
    Console.WriteLine($"Add data cost time : {stopwatch.ElapsedMilliseconds}");

    stopwatch.Restart();
    var data = BinarySearcher.Search_SortedList(sortedList, targetNumber);
    stopwatch.Stop();

    Console.WriteLine($"Find Result = {data}");
    Console.WriteLine($"Search Time : {stopwatch.ElapsedMilliseconds}ms");
}

開始測試

List<int> list = new List<int>();
int testNumber = 500000;
int targetNumber = 1500;
Console.WriteLine($"Test Number = {testNumber}");
ListTest(testNumber, targetNumber);
Console.WriteLine();
SortedListTest(testNumber, targetNumber);
Console.WriteLine();
Console.WriteLine();

testNumber = 2000;
Console.WriteLine($"Test Number = {testNumber}");
ListTest(testNumber, targetNumber);
Console.WriteLine();
SortedListTest(testNumber, targetNumber);

測試結果

https://ithelp.ithome.com.tw/upload/images/20210703/20114067XQ8emVFJSz.png

小結

Binary Search必須要先排序

  • List塞值不排,要做演算法時才排
  • SortdeList邊塞邊排,可直接使用驗算法

先看2000筆資料的比對
因為數值少,在毫秒內就處理完了,沒感覺。

不過在加大為500000筆資料後就有很大差距了
SortedList塞資料塞半天,超級放浪費時間
不過搜尋到是han快,畢竟已經排好了
List塞值很快,要做演算法前先才排序,所以浪費點時間。

依結果來看,用List就好了。 ̄ 3 ̄▂ξ

=============新增測試============
假如把原本的塞值testNumber到0改成0到testNumber的話

for (int i = testNumber; i >= 0; i--)
{
    sortedList.Add(i, i);
}

改成

for (int i = 0; i < testNumber; i++)
{
    sortedList.Add(i, i);
}

結果如下 :
https://ithelp.ithome.com.tw/upload/images/20210703/20114067OO17JJl99p.png
因為本來就排好排滿了,SortedList塞值變快很多,除非需要不斷的大量搜尋,不然...

依結果來看,還是用List就好了。 ̄ 3 ̄▂ξ

=============又新增測試了============
後來想到List只要Sort一次就好,不用每次都去Sort,所以測試了只Sort一次,之後的搜尋就直接用這個List去跑演算法。
跑出來結果Search Time大概會降到9ms左右

依結果來看,還是用List就好了。 ̄ 3 ̄▂ξ ̄ 3 ̄▂ξ

新手發文,若有錯誤的地方請不吝色的指正,謝謝。


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言